package SwordFingerOffer;

import java.util.*;

public class Q31_StackPushAndPop {
    //验证栈的压入弹出序列

    public boolean validateStackSequences(int[] pushed, int[] popped) {

        if (pushed == null || popped == null || pushed.length != popped.length){
            return false;
        }

        Stack<Integer> stack = new Stack<>();
        LinkedList<Integer> out = new LinkedList<>();
        for (int i = 0; i < popped.length; i++) {
            out.addLast(popped[i]);
        }

        for (int i = 0; i < pushed.length; i++) {
            if (pushed[i] != out.getFirst()){
                stack.add(pushed[i]);
            }else {
                out.removeFirst();
                //差了一步很关键 需要错误用例才发觉？
                while (stack.size() != 0 && out.size() != 0 && out.getFirst().equals(stack.peek())){
                    stack.pop();
                    out.removeFirst();
                }

            }
        }

        while (!stack.isEmpty() && out.size() != 0){
            if (!stack.pop().equals(out.pollFirst())){
                return false;
            }
        }
        if (!stack.isEmpty() || out.size() != 0){
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] push = new int[]{1,2,3,4,5};
        int[] pop = new int[]{4,5,3,2,1};
        Q31_StackPushAndPop fun = new Q31_StackPushAndPop();
        System.out.println(fun.validateStackSequences(push, pop));
    }
}
